1. Field of the Invention
This invention relates to computer network technology, and more particularly, to a computer network packet classification method and system based on a nonoverlapping rule group encoding scheme which is designed for integration to a network system for classification of packets transmitted and received over the network system.
2. Description of Related Art
Packet classification is an important function of network systems for applications such as firewalls and intrusion detection, policy-based routing, and network service differentiations, for use to identify the attributes of all incoming packets based on their headers. When a networking device, such as an enterprise-class server or router, receives an incoming packet, the first step is to determine the type of the packet, such as what protocol is being used by the packet, what ToS (Type of Service) or QoS (Quality of Service) is to be assigned to the packet, the source and destination of the packet (which might be used to indicate, for example, whether the packet is coming from a malignant source), to name just a few.
In actual implementation, packet classification is realized by using a user-predefined rule database which specifies the mapping of predefined field values in the packet header to a set of rules, each rule representing a particular type of action or service that is to be performed on the packet. For example, if the source IP address of an incoming packet is matched to a rule that specifies an unauthorized IP address, the action to be performed on the incoming packet might be to discard the packet or to trace back to its originating source.
Typically, the total number of rules in a rule database might be in the range from several dozens to several thousands. Therefore, the hardware/software implementation of packet classification typically requires a huge amount of memory space for storage of the rule database and also requires a significant amount of access time to search through the rule database for matched rules. This drawback causes the implementation of packet classification to have low system performance.
In view of the aforementioned problem, it has been a research effort in the computer network industry for solutions that can implement the packet classification with reduced memory space and enhanced access speed. Some research results have been disclosed in the following technical papers: [1] “High speed policy-based packet forwarding using efficient multidimensional range matching”, authored by T. V. Lakshman et al and published on Proc. ACM SIGCOMM. September 1998, pp. 191-202; [2] “Searching very large routing tables in fast sram”, authored by J. van Lunteren and published on Proc. IEEE ICCCN Conf., October 2002, pp. 4-11; and [3] “Searching very large routing tables in wide embedded memory”, authored by J. van Lunteren and published on Proc. IEEE GLOBECOM Conf., November 2001. vol. 3, pp. 1615-1619; to name just a few. Among these papers, the first paper [1] teaches the use of a so-called “lucent bit vector” for fast packet classification to find matched rules for the input packets. The second and third papers [2], [3] teach the use of a so-called “elementary interval”, or called “projected interval” for implementing fast packet classification. One drawback to these techniques, however, is that it still requires a significant amount of memory space for storage, and therefore still needs an improvement that can be implemented with a reduced memory space.